/*
 * ArrayOrderedSet.h
 *
 *  Created on: 18/09/2012
 *      Author: marcio
 */

#ifndef ARRAYORDEREDSET_H_
#define ARRAYORDEREDSET_H_

#include "OrderedSet.h"
#include "BitTools.h"
#include <stdio.h>

/*!
 * \class ArrayOrderedSet
 *
 * \brief A OrderedSet implemented with a array.
 *
 * This class represents a set with an order between its elements.
 *
 * It is a impletation of the abstract class OrderedSet with a linear
 * array as data structure.
 *
 * \tparam the type of the array
 */
template<typename T>
class ArrayOrderedSet : public OrderedSet<long>{

protected:

	long logb;//<! the log of the size of a word in bits.

	long logw;//<! the log of the size of a word in bytes.

	int sizeb;//<! the size of a word.

	long n;//<! the number of elements in the universe.

	long maskb;//<! a mask to determine the position of a bit in a word.

	T* vector;//<! the vector of words.

	long vectorsz;//<! the size of the word vector

public:

	/*!
	 * \brief The simple constructor.
	 *
	 * Calculate the size of the vector and allocate the memeory necessary.
	 *
	 * \param n the size of the universe
	 */
	 ArrayOrderedSet(long n);

	/*!
	 * \brief The simple destructor
	 *
	 * Free the memory used.
	 *
	 */
	 ~ArrayOrderedSet();

	 /*!
	  * \brief Create a copy of the current object.
	  *
	  * Copy the whole vector of bits to a other structure.
	  *
	  * \return a copy if the current object.
	  */
	 virtual OrderedSet<long>* clone();

	 /*!
	  * \brief A iterator to the set represented by this object.
	  *
	  * \return a iterator to the set representes by this object.
	  */
	 virtual OrderedSet<long>::Iterator* newSetIterator();

	 /*!
	  * \brief A iterator to the set represented by this object, filtered
	  * by a specified filter.
	  *
	  * \filter param the especified filter
	  *
	  * \return a iterator to the set representes by this object.
	  */
	 virtual OrderedSet<long>::Iterator* newSetIterator(OrderedSet<long>* filter);

	 /*!
	  * \brief A iterator to the complement of the set represented by this object.
	  *
	  * \return a iterator to the set representes by this object.
	  */
	 virtual OrderedSet<long>::Iterator* newComplIterator();

	 /*!
	  * \brief A iterator to the complement of the set represented by this object, filtered
	  * by a specified filter.
	  *
	  * \filter param the especified filter
	  *
	  * \return a iterator to the set representes by this object.
	  */
	 virtual OrderedSet<long>::Iterator* newComplIterator(OrderedSet<long>* filter);

	 /*!
	  * \brief Determine the smallest element in the set bigger than the specified
	  * element.
	  *
	  * Implemented as a linear search in the words of the array, using a buitin function
	  * to determinate the least position of a bit with value 1.
	  *
	  * \param i the specified element.
	  *
	  * \return the smallest element in the set bigger than the specified one.
	  */
	 virtual long nextSetElement(long i);

	 /*!
	  * \brief Determine the smallest element in the complement bigger than the specified
	  * element.
	  *
	  *	Implemented as a linear search in the words of the array, using a buitin function
	  * to determinate the least position of a bit with value 0.
	  *
	  * \param i the specified element.
	  *
	  * \return the smallest element in the complemet bigger than the specified one.
	  */
	 virtual long nextComplElement(long i);

	 /*!
	  * \brief Add the specified element to the set.
	  *
	  * Set the bit in the specified position to 1. This method is optmal and if the
	  * especified position is out of the vector range an error will occur.
	  *
	  * \param i the specified element.
	  */
	 virtual void toSet(long i);

	 /*!
	  * \brief Remove the specified element to the set.
	  *
	  *	Set the bit in the specified position to 0. This method is optmal and if the
	  * especified position is out of the vector range an error will occur.
	  *
	  * \param i the specified element
	  */
	 virtual void toCompl(long i);

	 /*!
	  * \brief Swap a element between the set and the complement.
	  *
	  * \param i the especified element.
	  */
	 virtual void swapElement(long i);

	 /*!
	  * \brief Verify if a element of the universe is in the set.
	  *
	  * Verify if the bit in the specified position is 1. This method is optmal and if the
	  * especified position is out of the vector range an error will occur.
	  *
	  * \param i the specified element
	  *
	  * \return true if i belongs to the set and false otherwise
	  */
	 virtual bool isInSet(long i);

	 /*!
	  * \brief Verify if a element of the universe is in the complement.
	  *
	  * Verify if the bit in the specified position is 0. This method is optmal and if the
	  * especified position is out of the vector range an error will occur.
	  *
	  * \param i the specified element
	  *
	  * \return true if i not belong to the set and false otherwise
	  */
	 virtual bool isInCompl(long i);

	 /*!
	  * \brief Create a vector of the elements in the set
	  *
	  * \param size a pointer to store the size of the set.
	  *
	  * \return a array contains all the elements of the set.
	  */
	 virtual long* toArray(long* size);

	 /*!
	  * \brief The size of the universe
	  *
	  * Return the size of the universe especified in the constructor.
	  *
	  * \return the size of the universe
	  */
	 virtual long size();

	 /*!
	  * \brief Verify if the set is empty
	  *
	  * Implemented as a linear search in each word of the vector testing if
	  * it was empty or not.
	  *
	  * \return true if the set is empty and false otherwise.
	  */
	 virtual bool isEmpty();

	 /*!
	  * \brief Add all the elements in the universe to the set
	  *
	  * Implemented with a C function memset.
	  *
	  * \see memset()
	  *
	  */
	 virtual void allToSet();

	 /*!
	  * \brief Remove all the elements of the set.
	  *
	  * Implemented with a C function memset.
	  *
	  * \see memset()
	  */
	 virtual void allToCompl();

	 /*!
	  * \brief The complement of the current set
	  *
	  * Implemented as a linear search in each word of the vector.
	  */
	 virtual void setComplement();

	 /*!
	  * \brief The complement of the current set, stored in the set res
	  *
	  * \param res the object to store the complement of the current set
	  * \see setComplement()
	  */
	 virtual void setComplement(ArrayOrderedSet<T> * res);

	 /*!
	  * \brief The complement of the current set, stored in the set res
	  *
	  * \param res the object to store the complement of the current set
	  * \see setComplement()
	  */
	 virtual void setComplement(OrderedSet<long> * res);

	 /*!
	  * \brief Union between the current set and the set represented by the object v
	  *
	  * This method overwrite the caller object with the result
	  *
	  * \param v the other set to be operated
	  */
	 virtual void setUnionSet(ArrayOrderedSet<T> * v);

	 /*!
	  * \brief Simetric Difference between the current set and the set represented by the object v
	  *
	  * This method overwrite the caller object with the result
	  *
	  * \param v the other set to be operated
	  */
	 virtual void setDiffSimetricSet(ArrayOrderedSet<T> * v);

	 /*!
	  * \brief Intersection between the current set and the set represented by the object v
	  *
	  * This method overwrite the caller object with the result
	  *
	  * \param v the other set to be operated
	  */
	 virtual void setIntersecSet(ArrayOrderedSet<T> * v);

	 /*!
	  * \brief Difference between the current set and the set represented by the object v
	  *
	  * This method overwrite the caller object with the result
	  *
	  * \param v the other set to be operated
	  */
	 virtual void setDiffSet(ArrayOrderedSet<T> * v);

	 /*!
	  * \brief Union between the current set and the set represented by the object v.
	  *
	  * \param v the other set to be operated
	  * \param res the set to store the result of the operation
	  *
	  * \see setUnionSet()
	  */
	 virtual void setUnionSet(ArrayOrderedSet<T> * v, ArrayOrderedSet<T> * res);

	 /*!
	  * \brief SimetricDifference between the current set and the set represented by the object v.
	  *
	  * \param v the other set to be operated
	  * \param res the set to store the result of the operation
	  *
	  * \see setDiffSimetricSet()
	  */
	 virtual void setDiffSimetricSet(ArrayOrderedSet<T> * v, ArrayOrderedSet<T> * res);

	 /*!
	  * \brief Intersection between the current set and the set represented by the object v.
	  *
	  * \param v the other set to be operated
	  * \param res the set to store the result of the operation
	  *
	  * \see setIntersecSet()
	  */
	 virtual void setIntersecSet(ArrayOrderedSet<T> * v, ArrayOrderedSet<T> * res);

	 /*!
	  * \brief Difference between the current set and the set represented by the object v
	  *
	  * \param v the other set to be operated
	  * \param res the set to store the result of the operation
	  *
	  * \see setDiffSet()
	  */
	 virtual void setDiffSet(ArrayOrderedSet<T> * v, ArrayOrderedSet<T> * res);

	 /*!
	  * \brief Union between the current complement and the set represented by the object v
	  *
	  * This method overwrite the caller object with the result.
	  *
	  * \param v the other set to be operated
	  */
	 virtual void complUnionSet(ArrayOrderedSet<T> * v);

	 /*!
	  * \brief Simetric Difference between the current complement and the set represented by the object v
	  *
	  * This method overwrite the caller object with the result
	  *
	  * \param v the other set to be operated
	  */
	 virtual void complDiffSimetricSet(ArrayOrderedSet<T> * v);

	 /*!
	  * \brief Intersection between the current complement and the set represented by the object v
	  *
	  * This method overwrite the caller object with the result
	  *
	  * \param v the other set to be operated
	  */
	 virtual void complIntersecSet(ArrayOrderedSet<T> * v);

	 /*!
	  * \brief Difference between the current complement and the set represented by the object v
	  *
	  *	 This method overwrite the caller object with the result
	  *
	  * \param v the other set to be operated
	  */
	 virtual void complDiffSet(ArrayOrderedSet<T> * v);

	 /*!
	  * \brief Union between the current complement and the set represented by the object v
	  *
	  * \param v the other set to be operated
	  *
	  * \param res the set to store the result of the operation
	  *
	  * \see complunionSet()
	  */
	 virtual void complUnionSet(ArrayOrderedSet<T> * v, ArrayOrderedSet<T> * res);

	 /*!
	  * \brief Simetric Difference between the current set and the set represented by the object v
	  *
	  * \param v the other set to be operated
	  *
	  * \param res the set to store the result of the operation
	  *
	  * \see complDiffSimetricSet()
	  */
	 virtual void complDiffSimetricSet(ArrayOrderedSet<T> * v, ArrayOrderedSet<T> * res);

	 /*!
	  * \brief Intersection between the current complement and the set represented by the object v
	  *
	  * \param v the other set to be operated
	  *
	  * \param res the set to store the result of the operation
	  *
	  * \see complIntersecSet()
	  */
	 virtual void complIntersecSet(ArrayOrderedSet<T> * v, ArrayOrderedSet<T> * res);

	 /*!
	  * \brief Difference between the current complement and the set represented by the object v
	  *
	  * \param v the other set to be operated
	  *
	  * \param res the set to store the result of the operation
	  *
	  * \see complDiffSet()
	  */
	 virtual void complDiffSet(ArrayOrderedSet<T> * v, ArrayOrderedSet<T> * res);

	 /*!
	  * \brief Union between the current set and the complement of the set represented by the object v
	  *
	  * This method overwrite the caller object with the result
	  *
	  * \param v the other set to be operated
	  */
	 virtual void setUnionCompl(ArrayOrderedSet<T> * v);

	 /*!
	  * \brief Simetric Difference between the current set and the complement of the set represented by the object v
	  *
	  * This method overwrite the caller object with the result
	  *
	  * \param v the other set to be operated
	  */
	 virtual void setDiffSimetricCompl(ArrayOrderedSet<T> * v);

	 /*!
	  * \brief Intersection between the current set and the complement of the set represented by the object v
	  *
	  * This method overwrite the caller object with the result
	  *
	  * \param v the other set to be operated
	  */
	 virtual void setIntersecCompl(ArrayOrderedSet<T> * v);

	 /*!
	  * \brief Difference between the current set and the set represented by the object v
	  *
	  * This method overwrite the caller object with the result
	  *
	  * \param v the other set to be operated
	  */
	 virtual void setDiffCompl(ArrayOrderedSet<T> * v);

	 /*!
	  * \brief Union between the current set and the complemnet of the set represented by the object v
	  *
	  * \param v the other set to be operated
	  *
	  * \param res the set to store the result of the operation
	  *
	  * \see setUnionCompl()
	  */
	 virtual void setUnionCompl(ArrayOrderedSet<T> * v, ArrayOrderedSet<T> * res);

	 /*!
	  * \brief Simetric Difference between the current set and the complemnet of the set represented by the object v
	  *
	  * \param v the other set to be operated
	  *
	  * \param res the set to store the result of the operation
	  *
	  * \see setDiffSimetricCompl()
	  */
	 virtual void setDiffSimetricCompl(ArrayOrderedSet<T> * v, ArrayOrderedSet<T> * res);

	 /*!
	  * \brief Intersect between the current set and the complemnet of the set represented by the object v
	  *
	  * \param v the other set to be operated
	  *
	  * \param res the set to store the result of the operation
	  *
	  * \see setIntersecCompl()
	  */
	 virtual void setIntersecCompl(ArrayOrderedSet<T> * v, ArrayOrderedSet<T> * res);

	 /*!
	  * \brief Diffence between the current set and the complemnet of the set represented by the object v
	  *
	  * \param v the other set to be operated
	  *
	  * \param res the set to store the result of the operation
	  *
	  * \see setDiffCompl()
	  */
	 virtual void setDiffCompl(ArrayOrderedSet<T> * v, ArrayOrderedSet<T> * res);

	 /*!
	  * \brief Union between the current complement and the compplement of the set represented by the object v
	  *
	  * This method overwrite the caller object with the result
	  *
	  * \param v the other set to be operated
	  */
	 virtual void complUnionCompl(ArrayOrderedSet<T> * v);

	 /*!
	  * \brief Simetric Difference between the current complement and the complement of the set represented by the object v
	  *
	  * This method overwrite the caller object with the result
	  *
	  * \param v the other set to be operated
	  */
	 virtual void complDiffSimetricCompl(ArrayOrderedSet<T> * v);

	 /*!
	  * \brief Intersection between the current complement and the complement of the set represented by the object v
	  *
	  * This method overwrite the caller object with the result
	  *
	  * \param v the other set to be operated
	  */
	 virtual void complIntersecCompl(ArrayOrderedSet<T> * v);

	 /*!
	  * \brief Difference between the current set and the set represented by the object v
	  *
	  * \param v the other set to be operated
	  */
	 virtual void complDiffCompl(ArrayOrderedSet<T> * v);

	 /*!
	  * \brief Union between the current complement and the complement of the set represented by the object v
	  *
	  * \param v the other set to be operated
	  *
	  * \param res the set to store the result of the operation
	  *
	  * \see complUnionCompl()
	  */
	 virtual void complUnionCompl(ArrayOrderedSet<T> * v, ArrayOrderedSet<T> * res);

	 /*!
	  * \brief Simetric Difference between the current complement and the complement of the set represented by the object v
	  *
	  * \param v the other set to be operated
	  *
	  * \param res the set to store the result of the operation
	  *
	  * \see complDiffSimetricCompl()
	  */
	 virtual void complDiffSimetricCompl(ArrayOrderedSet<T> * v, ArrayOrderedSet<T> * res);

	 /*!
	  * \brief intersect between the current complement and the complement of the set represented by the object v
	  *
	  * \param v the other set to be operated
	  *
	  * \param res the set to store the result of the operation
	  *
	  * \see complIntersecCompl()
	  */
	 virtual void complIntersecCompl(ArrayOrderedSet<T> * v, ArrayOrderedSet<T> * res);

	 /*!
	  * \brief Difference between the current complement and the complement of the set represented by the object v
	  *
	  * \param v the other set to be operated
	  *
	  * \param res the set to store the result of the operation
	  *
	  * \see complDiffCompl()
	  */
	 virtual void complDiffCompl(ArrayOrderedSet<T> * v, ArrayOrderedSet<T> * res);

	 /*!
	  * \brief Determine the first element of the set represented by the current object.
	  *
	  * Implemented as a linear search in each word of the vector.
	  *
	  * \return the first element in the set according to the total order.
	  */
	 virtual long firstInSet();

	 /*!
	  * \brief Determine the first element of the complement of the set represented by the current object.
	  *
	  * Implemented as a linear search in each word of the vector.
	  *
	  * \return the first element in the set according to the total order.
	  */
	 virtual long firstInCompl();

	 /*!
	  * \brief The cardinality of the set represented by the object.
	  *
	  * Implemented as a linear search in each word of the vector.
	  *
	  * \return the size of the current set.
	  */
	 virtual long cardOfSet();

	 /*!
	  * \brief The cardinality of the complement of the set represented by the object.
	  *
	  * Implemented as a linear search in each word of the vector.
	  *
	  * \return the size of the complement of the current set.
	  */
	 virtual long cardOfCompl();

	 //DEBUG
	 virtual void show();

};

template<typename T>
ArrayOrderedSet<T>::ArrayOrderedSet(long size){
	//determine the logs
	logw = inline_ceillog(sizeof(T), 1);
	logb = logw + 3;
	//edtermine the mask
	maskb = ~(-1L << logb);
	sizeb = 1LL << logb;
	n = size;
	//determine the size and allocate memory
	vectorsz = (n >> logb) + 1;
	vector = new T[vectorsz];
}

template<typename T>
ArrayOrderedSet<T>::~ArrayOrderedSet(){
	delete vector;
}

template<typename T>
inline OrderedSet<long>* ArrayOrderedSet<T>::clone(){
	ArrayOrderedSet<T>* ret = new ArrayOrderedSet<T>(n);
	T* retvec;
	T* vec;
	T* lim;
	for(retvec = ret->vector, vec = vector, lim = vector + vectorsz; vec < lim; vec++, retvec++){
		retvec = vec;
	}
	return ret;
}

template<typename T>
inline OrderedSet<long>::Iterator* ArrayOrderedSet<T>::newSetIterator(){
	//inner class to implement Iterator
	class Iterator : public OrderedSet<long>::Iterator{
		friend class ArrayOrderedSet<T>;
	private :
		ArrayOrderedSet<T>* t;// the set
		long current;//the current element
		long idx;// the index of the current's word
		long slide;// in the word the current's position
		long sizew;// size of each word
		long logw;// log two of sizew

	public:
		//constructor
		Iterator(ArrayOrderedSet<T>* set){
			t = set;
			current = 0;
			idx = 0;
			slide = 0;
			sizew = sizeof(T)*8;
			logw = set->logb;
		}

		//destructor
		~Iterator(){};

		//determine the first position of a bit 1
		void start(){
			long sz = t->vectorsz;
			T* vec = t->vector;
			idx = 0;
			slide = builtinLeast<T>(vec[idx]);
			while(idx < sz && slide == -1){
				idx++;
				slide = builtinLeast<T>(vec[idx]);
			}
			if(slide != -1) current = slide + (idx << logw);
			else current = -1;
		}

		//recall start
		void restart(){
			start();
		}

		//determine the first position after the specified one with a bit 1
		void restartFrom(long i){
			long sz = t->vectorsz;
			T* vec = t->vector;
			idx = i >> logw;
			slide = builtinLeast<T>(vec[idx] & posmasklsimp[i & t->maskb]);
			while(idx < t->vectorsz && slide == -1){
				idx++;
				slide = builtinLeast<T>(vec[idx]);
			}
			if(slide != -1) current = slide + (idx << logw);
			else current = -1;
		}

		//if current is less than zero it has no next element
		bool hasNext(){
			return current >= 0;
		}

		long next(){
			long ret = current;
			slide++;
			if(slide >= sizew){
				idx++;
				slide = 0;
			}
			long sz = t->vectorsz;
			T* vec = t->vector;
			slide = builtinLeast<T>(vec[idx] & posmasklsimp[slide]);
			while(idx < sz && slide == -1){
				idx++;
				slide = builtinLeast<T>(vec[idx]);
			}
			if(slide != -1 && idx < sz) current = slide + (idx << logw);
			else current = -1;
			return ret;
		}
	};
	return new Iterator(this);
}

template<typename T>
inline OrderedSet<long>::Iterator* ArrayOrderedSet<T>::newSetIterator(OrderedSet<long>* filter){
	class Iterator : public OrderedSet<long>::Iterator{
		friend class ArrayOrderedSet<T>;
	private :
		OrderedSet<long>* filter;// the filter
		ArrayOrderedSet<T>* t;// the set
		long current;//the current element
		long idx;// the index of the current's word
		long slide;// in the word the current's position
		long sizew;// size of each word
		long logw;// log two of sizew

	public:
		Iterator(ArrayOrderedSet<T>* set, OrderedSet<long>* fil){
			t = set;
			filter = fil;
			current = 0;
			idx = 0;
			slide = 0;
			sizew = sizeof(T)*8;
			logw = set->logb;
		}

		~Iterator(){};

		void start(){
			long sz = t->vectorsz;
			T* vec = t->vector;
			idx = 0;
			slide = builtinLeast<T>(vec[idx]);
			while(idx < sz && slide == -1){
				idx++;
				slide = builtinLeast<T>(vec[idx]);
				if(slide != -1 && filter->isInCompl((idx << logw)+ slide))slide = -1;
			}
			if(slide != -1) current = slide + (idx << logw);
			else current = -1;
		}

		void restart(){
			start();
		}

		void restartFrom(long i){
			long sz = t->vectorsz;
			T* vec = t->vector;
			idx = i >> logw;
			slide = builtinLeast<T>(vec[idx] & posmasklsimp[i & t->maskb]);
			while(idx < sz && slide == -1){
				idx++;
				slide = builtinLeast<T>(vec[idx]);
				if(slide != -1 && filter->isInCompl((idx << logw)+ slide))slide = -1;
			}
			if(slide != -1) current = slide + (idx << logw);
			else current = -1;
		}

		bool hasNext(){
			return current >= 0;
		}

		long next(){
			long ret = current;
			slide++;
			if(slide >= sizew){
				idx++;
				slide = 0;
			}
			long sz = t->vectorsz;
			T* vec = t->vector;
			slide = builtinLeast<T>(vec[idx] & posmasklsimp[slide]);
			while(idx < sz && slide == -1){
				idx++;
				slide = builtinLeast<T>(vec[idx]);
				if(slide != -1 && filter->isInCompl((idx << logw)+ slide))slide = -1;
			}
			if(slide != -1) current = slide + (idx << logw);
			else current = -1;
			return ret;
		}
	};
	return new Iterator(this, filter);
}

template<typename T>
inline OrderedSet<long>::Iterator* ArrayOrderedSet<T>::newComplIterator(){
	class Iterator : public OrderedSet<long>::Iterator{
		friend class ArrayOrderedSet<T>;
	private :
		ArrayOrderedSet<T>* t;// the set
		long current;//the current element
		long idx;// the index of the current's word
		long slide;// in the word the current's position
		long sizew;// size of each word
		long logw;// log two of sizew

	public:
		Iterator(ArrayOrderedSet<T>* set){
			t = set;
			current = 0;
			idx = 0;
			slide = 0;
			sizew = sizeof(T)*8;
			logw = set->logb;
		}

		~Iterator(){};

		void start(){
			long sz = t->vectorsz;
			T* vec = t->vector;
			idx = 0;
			slide = builtinLeast<T>(~vec[idx]);
			while(idx < sz && slide == -1){
				idx++;
				slide = builtinLeast<T>(~vec[idx]);
			}
			if(slide != -1) current = slide + (idx << logw);
			else current = -1;
		}

		void restart(){
			start();
		}

		void restartFrom(long i){
			long sz = t->vectorsz;
			T* vec = t->vector;
			idx = i >> logw;
			slide = builtinLeast<T>(~vec[idx] & posmasklsimp[i & t->maskb]);
			while(idx < t->vectorsz && slide == -1){
				idx++;
				slide = builtinLeast<T>(~vec[idx]);
			}
			if(slide != -1) current = slide + (idx << logw);
			else current = -1;
		}

		bool hasNext(){
			return current >= 0;
		}

		long next(){
			long ret = current;
			long sz = t->vectorsz;
			T* vec = t->vector;
			slide++;
			if(slide >= sizew){
				idx++;
				slide = 0;
			}
			slide = builtinLeast<T>(~vec[idx] & posmasklsimp[slide]);
			while(idx < sz && slide == -1){
				idx++;
				slide = builtinLeast<T>(~vec[idx]);
			}
			if(slide != -1) current = slide + (idx << logw);
			else current = -1;
			return ret;
		}
	};
	return new Iterator(this);
}

template<typename T>
inline OrderedSet<long>::Iterator* ArrayOrderedSet<T>::newComplIterator(OrderedSet<long>* filter){
	class Iterator : public OrderedSet<long>::Iterator{
		friend class ArrayOrderedSet<T>;
	private :
		OrderedSet<long>* filter;// the filter
		ArrayOrderedSet<T>* t;// the set
		long current;//the current element
		long idx;// the index of the current's word
		long slide;// in the word the current's position
		long sizew;// size of each word
		long logw;// log two of sizew

	public:
		Iterator(ArrayOrderedSet<T>* set, OrderedSet<long>* fil){
			t = set;
			filter = fil;
			current = 0;
			idx = 0;
			slide = 0;
			sizew = sizeof(T)*8;
			logw = set->logb;
		}

		~Iterator(){};

		void start(){
			long sz = t->vectorsz;
			T* vec = t->vector;
			idx = 0;
			slide = builtinLeast<T>(~vec[idx]);
			while(idx < sz && slide == -1){
				idx++;
				slide = builtinLeast<T>(~vec[idx]);
				if(slide != -1 && filter->isInCompl((idx << logw)+ slide))slide = -1;
			}
			if(slide != -1) current = slide + (idx << logw);
			else current = -1;
		}

		void restart(){
			start();
		}

		void restartFrom(long i){
			long sz = t->vectorsz;
			T* vec = t->vector;
			idx = i >> logw;
			slide = builtinLeast<T>(~vec[idx] & posmasklsimp[i & t->maskb]);
			while(idx < sz && slide == -1){
				idx++;
				slide = builtinLeast<T>(~vec[idx]);
				if(slide != -1 && filter->isInCompl((idx << logw)+ slide))slide = -1;
			}
			if(slide != -1) current = slide + (idx << logw);
			else current = -1;
		}

		bool hasNext(){
			return current >= 0;
		}

		long next(){
			long ret = current;
			long sz = t->vectorsz;
			T* vec = t->vector;
			slide++;
			if(slide >= sizew){
				idx++;
				slide = 0;
			}
			slide = builtinLeast<T>(~vec[idx] & posmasklsimp[slide]);
			while(idx < sz && slide == -1){
				idx++;
				slide = builtinLeast<T>(~vec[idx]);
				if(slide != -1 && filter->isInCompl((idx << logw)+ slide))slide = -1;
			}
			if(slide != -1) current = slide + (idx << logw);
			else current = -1;
			return ret;
		}
	};
	return new Iterator(this, filter);
}

template<>
inline long ArrayOrderedSet<int>::nextSetElement(long i){
	long index = i >> logb;
	long slide = i & maskb;
	long ret = builtinLeast<int>(vector[index] & posmasksimp[slide]);
	if(ret != -1) return (index << logb) + ret;
	index++;
	while(ret == -1 && index < vectorsz){
		ret = builtinLeast<int>(vector[index]);
		index++;
	}
	return (index << logb) + ret;
}

template<>
inline long ArrayOrderedSet<long>::nextSetElement(long i){
	long index = i >> logb;
	long slide = i & maskb;
	long ret = builtinLeast<long>(vector[index] & posmasklsimp[slide]);
	if(ret != -1) return (index << logb) + ret;
	index++;
	while(ret == -1 && index < vectorsz){
		ret = builtinLeast<long>(vector[index]);
		index++;
	}
	return (index << logb) + ret;
}

template<>
inline long ArrayOrderedSet<int>::nextComplElement(long i){
	long index = i >> logb;
	long slide = i & maskb;
	long ret = builtinLeast<int>((~vector[index]) & (~posmasksimp[slide]));
	if(ret != -1) return (index << logb) + ret;
	index++;
	while(ret == -1 && index < vectorsz){
		ret = builtinLeast<int>(~vector[index]);
		index++;
	}
	return (index << logb) + ret;
}

template<>
inline long ArrayOrderedSet<long>::nextComplElement(long i){
	long index = i >> logb;
	long slide = i & maskb;
	long ret = builtinLeast<long>((~vector[index]) & (~posmasklsimp[slide]));
	if(ret != -1) return (index << logb) + ret;
	index++;
	while(ret == -1 && index < vectorsz){
		ret = builtinLeast<long>(~vector[index]);
		index++;
	}
	return (index << logb) + ret;
}

template<typename T>
inline void ArrayOrderedSet<T>::toSet(long i){
	vector[i >> logb] |= (1LL << (i & maskb));
}

template<typename T>
inline void ArrayOrderedSet<T>::toCompl(long i){
	vector[i >> logb] &= ~(1LL << (i & maskb));
}

template<typename T>
inline void ArrayOrderedSet<T>::swapElement(long i){
	if(isInSet(i)) toCompl(i);
	else toSet(i);
}

template<typename T>
inline bool ArrayOrderedSet<T>::isInSet(long i){
	return (vector[i >> logb] & (1LL << (i & maskb))) != 0;
}

template<typename T>
inline bool ArrayOrderedSet<T>::isInCompl(long i){
	return (vector[i >> logb] & (1LL << (i & maskb))) == 0;
}

template<typename T>
inline long* ArrayOrderedSet<T>::toArray(long* size){
	T* ret = new T[vectorsz];
	T* vec = vector;
	T* lim = vec + vectorsz;
	for(; vec < lim; vec++, ret++) *ret = *vec;
	return (long*)ret;
}

template<typename T>
inline long ArrayOrderedSet<T>::size(){
	return n;
}

template<typename T>
inline bool ArrayOrderedSet<T>::isEmpty(){
	return cardOfSet() == 0;
}

template<typename T>
inline void ArrayOrderedSet<T>::allToSet(){
	memset(vector, 255, vectorsz*sizeof(T));
}

template<typename T>
inline void ArrayOrderedSet<T>::allToCompl(){
	memset(vector, 0, vectorsz*sizeof(T));
}

template<typename T>
inline void ArrayOrderedSet<T>::setComplement(){
	T* vec, *lim;
	for(vec = vector, lim = vector + vectorsz; vec < lim; vec++ ) *vec = ~(*vec);
}

template<typename T>
inline void ArrayOrderedSet<T>::setComplement(ArrayOrderedSet<T> * res){
	T* vec, *lim, *ret;
	for(ret = res->vector, vec = vector, lim = vector + vectorsz; vec < lim; vec++, ret++ ) *ret = ~(*vec);
}

template<typename T>
inline void ArrayOrderedSet<T>::setComplement(OrderedSet<long> * res){
	for(long i = 0; i < n; i++){
		if(isInCompl(i))res->toSet(i);
		else res->toCompl(i);
	}
}


template<typename T>
inline void ArrayOrderedSet<T>::setUnionSet(ArrayOrderedSet<T> * v){
	T* va, *vb, *lim, *ret;
	for(ret = vector, va = vector, vb = v->vector, lim = vector + vectorsz; va < lim; va++, vb++, ret++)
		*ret = *va | *vb;
}

template<typename T>
inline void ArrayOrderedSet<T>::setDiffSimetricSet(ArrayOrderedSet<T> * v){
	T* va, *vb, *lim, *ret;
	for(ret = vector, va = vector, vb = v->vector, lim = vector + vectorsz; va < lim; va++, vb++, ret++)
		*ret = *va ^ *vb;
}

template<typename T>
inline void ArrayOrderedSet<T>::setIntersecSet(ArrayOrderedSet<T> * v){
	T* va, *vb, *lim, *ret;
	for(ret = vector, va = vector, vb = v->vector, lim = vector + vectorsz; va < lim; va++, vb++, ret++)
		*ret = *va & *vb;
}

template<typename T>
inline void ArrayOrderedSet<T>::setDiffSet(ArrayOrderedSet<T> * v){
	for(long i = 0; i < n; i++){
		if(v->isInSet(i))toCompl(i);
	}
}

template<typename T>
inline void ArrayOrderedSet<T>::setUnionSet(ArrayOrderedSet<T> * v, ArrayOrderedSet<T> * res){
	T* va, *vb, *lim, *ret;
	for(ret = res->vector, va = vector, vb = v->vector, lim = vector + vectorsz; va < lim; va++, vb++, ret++)
		*ret = *va | *vb;
}

template<typename T>
inline void ArrayOrderedSet<T>::setDiffSimetricSet(ArrayOrderedSet<T> * v, ArrayOrderedSet<T> * res){
	T* va, *vb, *lim, *ret;
	for(ret = res->vector, va = vector, vb = v->vector, lim = vector + vectorsz; va < lim; va++, vb++, ret++)
		*ret = *va ^ *vb;
}

template<typename T>
inline void ArrayOrderedSet<T>::setIntersecSet(ArrayOrderedSet<T> * v, ArrayOrderedSet<T> * res){
	T* va, *vb, *lim, *ret;
	for(ret = res->vector, va = vector, vb = v->vector, lim = vector + vectorsz; va < lim; va++, vb++, ret++)
		*ret = *va & *vb;
}

template<typename T>
inline void ArrayOrderedSet<T>::setDiffSet(ArrayOrderedSet<T> * v, ArrayOrderedSet<T> * res){
	for(long i = 0; i < n; i++){
		if(v->isInCompl(i)&& isInSet(i)) res->toSet(i);
	}
}

template<typename T>
inline void ArrayOrderedSet<T>::complUnionSet(ArrayOrderedSet<T> * v){
	T* va, *vb, *lim, *ret;
	for(ret = vector, va = vector, vb = v->vector, lim = vector + vectorsz; va < lim; va++, vb++, ret++)
		*ret = ~*va | *vb;
}

template<typename T>
inline void ArrayOrderedSet<T>::complDiffSimetricSet(ArrayOrderedSet<T> * v){
	T* va, *vb, *lim, *ret;
	for(ret = vector, va = vector, vb = v->vector, lim = vector + vectorsz; va < lim; va++, vb++, ret++)
		*ret = ~*va ^ *vb;
}

template<typename T>
inline void ArrayOrderedSet<T>::complIntersecSet(ArrayOrderedSet<T> * v){
	T* va, *vb, *lim, *ret;
	for(ret = vector, va = vector, vb = v->vector, lim = vector + vectorsz; va < lim; va++, vb++, ret++)
		*ret = ~*va & *vb;
}

template<typename T>
inline void ArrayOrderedSet<T>::complDiffSet(ArrayOrderedSet<T> * v){
	complIntersecSet(v);
}

template<typename T>
inline void ArrayOrderedSet<T>::complUnionSet(ArrayOrderedSet<T> * v, ArrayOrderedSet<T> * res){
	T* va, *vb, *lim, *ret;
	for(ret = res->vector, va = vector, vb = v->vector, lim = vector + vectorsz; va < lim; va++, vb++, ret++)
		*ret = ~*va | *vb;
}

template<typename T>
inline void ArrayOrderedSet<T>::complDiffSimetricSet(ArrayOrderedSet<T> * v, ArrayOrderedSet<T> * res){
	T* va, *vb, *lim, *ret;
	for(ret = res->vector, va = vector, vb = v->vector, lim = vector + vectorsz; va < lim; va++, vb++, ret++)
		*ret = ~*va ^ *vb;
}

template<typename T>
inline void ArrayOrderedSet<T>::complIntersecSet(ArrayOrderedSet<T> * v, ArrayOrderedSet<T> * res){
	T* va, *vb, *lim, *ret;
	for(ret = res->vector, va = vector, vb = v->vector, lim = vector + vectorsz; va < lim; va++, vb++, ret++)
		*ret = ~*va & *vb;
}

template<typename T>
inline void ArrayOrderedSet<T>::complDiffSet(ArrayOrderedSet<T> * v, ArrayOrderedSet<T> * res){
	complIntersecSet(v,res);
}

template<typename T>
inline void ArrayOrderedSet<T>::setUnionCompl(ArrayOrderedSet<T> * v){
	T* va, *vb, *lim, *ret;
	for(ret = vector, va = vector, vb = v->vector, lim = vector + vectorsz; va < lim; va++, vb++, ret++)
		*ret = *va | ~*vb;
}

template<typename T>
inline void ArrayOrderedSet<T>::setDiffSimetricCompl(ArrayOrderedSet<T> * v){
	T* va, *vb, *lim, *ret;
	for(ret = vector, va = vector, vb = v->vector, lim = vector + vectorsz; va < lim; va++, vb++, ret++)
		*ret = *va ^ ~*vb;
}

template<typename T>
inline void ArrayOrderedSet<T>::setIntersecCompl(ArrayOrderedSet<T> * v){
	T* va, *vb, *lim, *ret;
	for(ret = vector, va = vector, vb = v->vector, lim = vector + vectorsz; va < lim; va++, vb++, ret++)
		*ret = *va | ~*vb;
}

template<typename T>
inline void ArrayOrderedSet<T>::setDiffCompl(ArrayOrderedSet<T> * v){
	setIntersecCompl(v);
}

template<typename T>
inline void ArrayOrderedSet<T>::setUnionCompl(ArrayOrderedSet<T> * v, ArrayOrderedSet<T> * res){
	T* va, *vb, *lim, *ret;
	for(ret = res->vector, va = vector, vb = v->vector, lim = vector + vectorsz; va < lim; va++, vb++, ret++)
		*ret = *va | ~*vb;
}

template<typename T>
inline void ArrayOrderedSet<T>::setDiffSimetricCompl(ArrayOrderedSet<T> * v, ArrayOrderedSet<T> * res){
	T* va, *vb, *lim, *ret;
	for(ret = res->vector, va = vector, vb = v->vector, lim = vector + vectorsz; va < lim; va++, vb++, ret++)
		*ret = *va ^ ~*vb;
}

template<typename T>
inline void ArrayOrderedSet<T>::setIntersecCompl(ArrayOrderedSet<T> * v, ArrayOrderedSet<T> * res){
	T* va, *vb, *lim, *ret;
	for(ret = res->vector, va = vector, vb = v->vector, lim = vector + vectorsz; va < lim; va++, vb++, ret++)
		*ret = *va & ~*vb;
}

template<typename T>
inline void ArrayOrderedSet<T>::setDiffCompl(ArrayOrderedSet<T> * v, ArrayOrderedSet<T> * res){
	setIntersecCompl(v,res);
}

template<typename T>
inline void ArrayOrderedSet<T>::complUnionCompl(ArrayOrderedSet<T> * v){
	T* va, *vb, *lim, *ret;
	for(ret = vector, va = vector, vb = v->vector, lim = vector + vectorsz; va < lim; va++, vb++, ret++)
		*ret = ~*va | ~*vb;
}

template<typename T>
inline void ArrayOrderedSet<T>::complDiffSimetricCompl(ArrayOrderedSet<T> * v){
	T* va, *vb, *lim, *ret;
	for(ret = vector, va = vector, vb = v->vector, lim = vector + vectorsz; va < lim; va++, vb++, ret++)
		*ret = ~*va ^ ~*vb;
}

template<typename T>
inline void ArrayOrderedSet<T>::complIntersecCompl(ArrayOrderedSet<T> * v){
	T* va, *vb, *lim, *ret;
	for(ret = vector, va = vector, vb = v->vector, lim = vector + vectorsz; va < lim; va++, vb++, ret++)
		*ret = ~*va & ~*vb;
}

template<typename T>
inline void ArrayOrderedSet<T>::complDiffCompl(ArrayOrderedSet<T> * v){
	for(long i = 0; i < n; i++){
		if(v->isInSet(i) && isInCompl(i))toSet(i);
	}
}

template<typename T>
inline void ArrayOrderedSet<T>::complUnionCompl(ArrayOrderedSet<T> * v, ArrayOrderedSet<T> * res){
	T* va, *vb, *lim, *ret;
	for(ret = res->vector, va = vector, vb = v->vector, lim = vector + vectorsz; va < lim; va++, vb++, ret++)
		*ret = ~*va | ~*vb;
}

template<typename T>
inline void ArrayOrderedSet<T>::complDiffSimetricCompl(ArrayOrderedSet<T> * v, ArrayOrderedSet<T> * res){
	T* va, *vb, *lim, *ret;
	for(ret = res->vector, va = vector, vb = v->vector, lim = vector + vectorsz; va < lim; va++, vb++, ret++)
		*ret = ~*va ^ ~*vb;
}

template<typename T>
inline void ArrayOrderedSet<T>::complIntersecCompl(ArrayOrderedSet<T> * v, ArrayOrderedSet<T> * res){
	T* va, *vb, *lim, *ret;
	for(ret = res->vector, va = vector, vb = v->vector, lim = vector + vectorsz; va < lim; va++, vb++, ret++)
		*ret = ~*va & ~*vb;
}

template<typename T>
inline void ArrayOrderedSet<T>::complDiffCompl(ArrayOrderedSet<T> * v, ArrayOrderedSet<T> * res){
	for(long i = 0; i < n; i++){
		if(v->isInSet(i) && isInCompl(i))res->toSet(i);
	}
}

template<typename T>
inline long ArrayOrderedSet<T>::firstInSet(){
	long ret;
	for(long i = 0; i < vectorsz; i++){
		ret = builtinLeast<T>(vector[i]);
		if(ret >=0) return (i<< logb) + ret;
	}
	return n+1;
}

template<typename T>
inline long ArrayOrderedSet<T>::firstInCompl(){
	long ret;
	for(long i = 0; i < vectorsz; i++){
		ret = builtinLeast<T>(~vector[i]);
		if(ret >=0) return (i<< logb) + ret;
	}
	return n+1;
}

template<typename T>
inline long ArrayOrderedSet<T>::cardOfSet(){
	long ret;
	T* vec, *lim;
	for(vec = vector,lim = vector + vectorsz; vec < lim; vec++){
		ret += builtinCounter<T>(*vec);
	}
	return ret;
}

template<typename T>
inline long ArrayOrderedSet<T>::cardOfCompl(){
	long ret;
	T* vec, *lim;
	for(vec = vector, lim = vector + vectorsz; vec < lim; vec++){
		ret += builtinCounter<T>(~*vec);
	}
	return ret;
}

template<typename T>
inline void ArrayOrderedSet<T>::show(){
	printf("vetor \n");
	for(long i = 0; i < n; i++)
		if(isInSet(i))printf("<%lu> ", i);
	printf("\n");
}

template <typename T>
class ArrayOrderedSetFactory : public OrderedSetFactory<long>{
public:

	OrderedSet<long>* newOrderedSet(long n){
		return (OrderedSet<long>*) new ArrayOrderedSet<T>(n);
	};

	OrderedSet<long>* newOrderedSet(long n, void* handle){
		return (OrderedSet<long>*)new ArrayOrderedSet<T>(n);
	};

};

#endif /* ARRAYORDEREDSET_H_ */
